/**
 * @file 455.AssignCookies.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-28
 * 
 * @copyright Copyright (c) 2021
 * 
 * 贪心算法
 * 1 常见问题：分发饼干。。。
 * 2 区间问题：无重叠区间
 * 3 其他问题
 * 
 * 455.分发饼干
 * 376.摆动序列
 * 53.最大子序和
 * 122.买卖股票II
 * 
 * 分发糖果
 * 406.根据身高重建队列
 * 
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    cout << '[';
    while (it != Containers.end()) {
        cout << *it << ", ";
        ++it;
    }
    cout << ']';
    cout << endl;
}

class Solution
{
public:
    // 435.
    int findContentChildren(vector<int> &g, vector<int> &s)
    {
        std::sort(g.begin(), g.end());
        std::sort(s.begin(), s.end());
        int cnt = 0;
        int j = 0;
        while (cnt < g.size() && j < s.size()) {
            if (s[j] >= g[cnt]) {
                ++cnt;
            }
            ++j;
        }
        return cnt;
    }
    // 376.连续数字之间的差严格正负交替：摆动序列
    // 求最长摆动子序列长度
    int wiggleMaxLength(const vector<int> &nums)
    {
        int preDiff = 0;
        int curDiff = 0;
        int length = 1;
        for (int i = 1; i < nums.size(); ++i) {
            curDiff = nums[i] - nums[i - 1];
            if (curDiff > 0 && preDiff <= 0 || curDiff < 0 && preDiff >= 0) {
                ++length;
                preDiff = curDiff;
            }
        }
        return length;
    }
    // 53.最大子序和
    int maxSubArray(const vector<int> &nums)
    {
        // 贪心，局部最优：连续和变成负立即重新开始计算
        int n = nums.size();
        int sum = 0;
        int res = INT32_MIN;
        for (int i = 0; i < n; ++i) {
            if (sum < 0) {
                sum = 0;
            }
            sum += nums[i];
            res = max(res, sum);
        }
        return res;
    }
    // 122.买卖股票II：不限买卖次数
    int maxProfit(vector<int> &prices)
    {
        // 贪心：只要每天利润就买卖
        int n = prices.size();
        int res = 0;
        for (int i = 1; i < n; ++i) {
            res += max(prices[i] - prices[i - 1], 0);
        }
        return res;
    }
};

void test455()
{
    vector<int> g1 = {1, 2, 3};
    vector<int> s1 = {1, 1};
    vector<int> g2 = {10, 9, 8, 7};
    vector<int> s2 = {5, 6, 7, 8};
    cout << Solution().findContentChildren(g1, s1) << endl;
    cout << Solution().findContentChildren(g2, s2) << endl;
}

void test376()
{
    cout << Solution().wiggleMaxLength({1, 7, 4, 9, 2, 5}) << endl;
    cout << Solution().wiggleMaxLength({1, 17, 5, 10, 13, 15, 10, 5, 16, 8}) << endl;
    cout << Solution().wiggleMaxLength({1, 2, 3, 4, 5, 6, 7, 8, 9}) << endl;
}

void test53()
{
    cout << Solution().maxSubArray({-2, 1, -3, 4, -1, 2, 1, -5, 4}) << endl;
    cout << Solution().maxSubArray({-10000}) << endl;
    cout << Solution().maxSubArray({1}) << endl;
    cout << Solution().maxSubArray({0}) << endl;
}

void test122()
{
    vector<int> nums1 = {7, 1, 5, 3, 6, 4};
    vector<int> nums2 = {1, 2, 3, 4, 5};
    vector<int> nums3 = {7, 6, 4, 3, 1};
    cout << Solution().maxProfit(nums1) << endl;
    cout << Solution().maxProfit(nums2) << endl;
    cout << Solution().maxProfit(nums3) << endl;
}

void test406()
{
    vector<vector<int>> nums1 = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
    vector<vector<int>> nums2 = {{6, 0}, {5, 0}, {4, 0}, {3, 2}, {2, 2}, {1, 4}};
    cout << Solution().eraseOverlapIntervals(nums1) << endl;
    cout << Solution().eraseOverlapIntervals(nums2) << endl;
}

int main()
{
    // test455();
    // test376();
    // test53();
    test122();
    return 0;
}